package com.zj.leetcode.medium.binarySearch;

/**
 * @program: algorithm
 * @description:
 * 寻找旋转排序数组中的最小值
 * 153 find-minimum-in-rotated-sorted-array
 * @author: Zhang Bo
 * @create: 2022-04-26 19:56:28
 **/
public class FindMinimumInRotatedSortedArray{
    public static void main(String[] args) {
        Solution solution = new FindMinimumInRotatedSortedArray().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int findMin(int[] nums) {
            int min = Integer.MAX_VALUE;
            for (int i = 0; i < nums.length; i++) {
                min = Math.min(nums[i], min);
            }

            return min;
        }

        /**
         * 【二分最清晰的理解】这道题的二分解法一开始也困扰了我很久，总所周知二分的逻辑非常简单，难点在边界处理。
         * 这道题我说说自己的理解， 首先二分的根本是有序，只要有序就能二分，哪怕是部分有序（这个是重点！！）
         * 我们先搞清楚题目中的数组是通过怎样的变化得来的，基本上就是等于将整个数组向右平移（想象一个圆形的环）。
         * 重点来了，不管怎么移，数组总有一半是有序的！！要么左半边完全有序，要么右半边完全有序。
         * 那么大家可以想想，最小值在有序的那半边还是无序的那半边。答案很显然是在无序的那半边（想想数组是如何变化得来的）。
         * 那就很简单了，每一次二分都找无序的那一半，到最后剩下的就是最小值。
         * @param nums
         * @return
         */
        public int findMin01(int[] nums) {
            int first = nums[0];

            int l = 0;
            int r = nums.length;

            while (l <= r){
                int mid = (r - l) / 2 + l;
                if(nums[mid] < nums[mid - 1]
                        && nums[mid] < nums[mid + 1]){
                    return nums[mid];
                } else {
                    if(first < nums[mid]){
                        r = mid + 1;
                    } else {
                        l = mid - 1;
                    }
                }
            }
            return nums[0];
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}